#include<stdio.h>
#include<stdlib.h>

#define MVNum 100   //最大顶点数
#define MaxInt 32767   //表示无穷的极大值
#define true 1
#define false 0

typedef struct 
{
    char vexs[MVNum];  // 顶点表--> 存储的数据(char型)
    int arcs[MVNum][MVNum];  //邻接矩阵
    int vexNum,arcNum;   //图的点数和边数
}AMGraph;

/*
采用邻接矩阵创建无向网
1.输入总顶点数和总边数
2.依次输入点的信息存入顶点表中
3.初始化邻接矩阵，使每个权值为最大值
4.构造邻接矩阵
*/

int Location(AMGraph* graph,char V)
{
    for(int i=0;i<graph->vexNum;i++)
    {
        if(graph->vexs[i]==V)
        {
            return i;
        }
    }
    return false;
}

void CreatUDN(AMGraph* graph)
{
    char v1,v2;  // 记录两个临时顶点
    printf("输入图的点数和边数\n");
    scanf("%d %d",&graph->vexNum,&graph->arcNum);
    getchar();
    for(int i=0;i<graph->vexNum;i++)
    {
        printf("输入各顶点的数据\n");
        scanf("%c",&graph->vexs[i]);    //依次输入顶点的信息
        getchar();
    }
    for(int i=0;i<graph->arcNum;i++)
    {
        for(int j=0;j<graph->arcNum;j++)
        {
            graph->arcs[i][j]=MaxInt;
        }
    }
    int k,L,w;
    for (int i = 0; i < graph->arcNum; i++)
    {
        printf("输入边的两个顶点和权值:\n");
        getchar();
        scanf("%c %c %d",&v1,&v2,&w);
        // 确定V1、V2 在G中的位置  
        k=Location(graph,v1);
        L=Location(graph,v2);  
        graph->arcs[k][L]=w;
        // 对称赋值
        graph->arcs[L][k]=w;

    }
    return true;
    
}

// 深度优先遍历
void deepSearch(AMGraph* graph,int* visited,int index)
{
    visited[index]=1;
    printf("%c\t",graph->vexs[index]);
    for(int i=0;i<graph->vexNum;i++)
    {
        if((graph->arcs[index][i]!=MaxInt)&&(!visited[i]))
        {
            deepSearch(graph,visited,i);
        }
    }
}

void main()
{
    AMGraph graph;
    CreatUDN(&graph);
    int visited[5]={0};
    deepSearch(&graph,visited,1);

}